﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using snat.model;

namespace algorithms.Utils.Metrics
{
    /// <summary>
    /// This file contains a selection of the simple link prediction metrics in the paper
    /// "The Link Prediction Problem for Social Networks" by Kleinberg and Liben-Nowell.
    /// It is available at http://www.cs.cornell.edu/home/kleinber/link-pred.pdf
    /// As well as a simple cosine similarity statistic.
    /// </summary>


    public static class LinkPredictionMetrics
    {

        /// <summary>
        ///     Computes the size of the set of common neighbors between two BaseNodes.
        ///     Nodes with more common neighbors are more likely to form links themselves.
        /// </summary>
        /// <param name="a">A BaseNode</param>
        /// <param name="b">A BaseNode</param>
        /// <returns></returns>
        public static int CommonNeighbors(BaseNode a, BaseNode b) {

            IEnumerable<BaseNode> aNeighbors = from edge in a.OverlayEdges
                                               select edge.Source == a ? edge.Target : edge.Source;

            IEnumerable<BaseNode> bNeighbors = from edge in b.OverlayEdges
                                               select edge.Source == b ? edge.Target : edge.Source;

            return aNeighbors.Intersect(bNeighbors).Count();
        }

        /// <summary>
        /// Jaccards coefficient is a measure of the likelihood that two nodes share a randomly selected
        /// feature that either of them already has.
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static double JaccardsCoefficient(BaseNode a, BaseNode b) {
            IEnumerable<BaseNode> aNeighbors = from edge in a.OverlayEdges
                                               select edge.Source == a ? edge.Target : edge.Source;

            IEnumerable<BaseNode> bNeighbors = from edge in b.OverlayEdges
                                               select edge.Source == b ? edge.Target : edge.Source;

            return ((double) aNeighbors.Intersect(bNeighbors).Count())
                     / ((double) aNeighbors.Union(bNeighbors).Count());
        }


        /// <summary>
        /// The Adamic/Adar is related to Jaccards Coefficient, with the extension that it rates
        /// rare features more heavily.
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static double AdamicAdar(BaseNode a, BaseNode b) {
            IEnumerable<BaseNode> aNeighbors = from edge in a.OverlayEdges
                                               select edge.Source == a ? edge.Target : edge.Source;

            IEnumerable<BaseNode> bNeighbors = from edge in b.OverlayEdges
                                               select edge.Source == b ? edge.Target : edge.Source;

            
            IEnumerable<BaseNode> commonFeatures = aNeighbors.Intersect(bNeighbors);
            return commonFeatures.Sum(e => 1.0 / Math.Log((double)e.OverlayDegree));
        }

        /// <summary>
        /// Preferrential Attachment is used heavily in a model of the growth of networks.
        /// It is the simply the product of the degrees of both nodes.
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static int PreferentialAttachment(BaseNode a, BaseNode b) {
            return a.OverlayDegree * b.OverlayDegree;
        }


        /// <summary>
        /// Returns the cosine similarity over the neighbourhoods of the two nodes.
        /// Note - the vector dot product
        ///
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static double CosineSimilarity(BaseNode a, BaseNode b) {
            return ((double)CommonNeighbors(a, b) / Math.Sqrt(a.OverlayDegree) * Math.Sqrt(b.OverlayDegree));
            //the number of natches
            //sqrt(the number of 
        }









    }
}
